Приватний навчальний заклад “Галицька академія” Кафедра комп’ютерної та програмної інженерії КУРСОВА РОБОТА з дисципліни: “Основи дискретної математики” Тема: «Алгоритм Дейкстра» ПОЯСНЮВАЛЬНА ЗАПИСКА КР.ПІ- 59. 00. 00. 000. ПЗ Студент групи ПІ-08 __________ (Вовчук С.П.) (підпис) Допускається до захисту Керівник курсового проекту Доцент (Мельничук С.І.) (посада) (підпис) (дата) (розшифровка підпису) м. Івано-Франківськ 2011 Аннотація В курсовій роботі проаналізовані основні поняття і визначення, типи графів, алгоритм Дейкстра, опис і виконання програми написаної на основі алгоритму Дейкстра. Summary In term paper analyzed the basic concepts and definitions, types of graphs, Daycstra's algorithm, the program description and written by Daycstra's algorithm.Зміст 1.Вступ..………………………………………………...………………..…………3 2.Елементи теорії графів:Основні визначення.……………………..………………………..…………..3Ізоморфізм, гомеоморфізм..……………………………………….…………4 Шляхи і цикли……………..……………………………………….…………5Дерева…...……………………………………………………………………..5Цикломатичне число і фундаментальні цикли………….…………………..8Компланарні графи …………………………………………………..……….8Розфарбування графів…...……………………………………………….….10 Графи з атрибутами ……………………...………………………….………12Незалежні безлічі і покриття …………………...……………………..……12 3.Задача знаходження мінімального шляху в графах: Алгоритм Дейкстра……..……………………………………….…..………14 Текст програми написаної на основі алгоритму Дейкстра……………….15 Результат виконання програми…………...………………………………...17Графічне зображення початкового графа та дерево мінімальних шляхів після виконання програми………………..……………………….……..…18 4.Висновок…………………………………………….………………………….18 5. Література ………………………………………………………..…….……..19   1. Вступ Останнім часом дослідження в областях, що традиційно відносяться до дискретної математики, займають усе більш помітне місце. Поряд з такими класичними розділами математики, як математичний аналіз, диференціальні рівняння, у навчальних планах спеціальності "Прикладна математика" і багатьох інших спеціальностей з'явилися розділи по математичній логіці, алгебрі, комбінаториці і теорії графів. Причини цього неважко зрозуміти, просто розглянувши задачу, розв'язувану пошуку найкоротшого шляху в графі. 2. Елементи теорії графів Основні визначення Граф (graph) - пари G=(V,E), де V - безліч об'єктів довільної природи, називаних вершинами (vertices, nodes), а E - сімейство пар ei=(vi1, vi2), vijV, називаних ребрами (edges). У загальному випадку безліч V і/чи сімейство E можуть містити нескінченне число елементів, але ми будемо розглядати тільки кінцеві графи, тобто графи, у яких як V, так і E кінцеві. У приведеному визначенні графа E не випадково названо сімейством пар, а не безліччю. Справа в тім, що елементи E можуть бути не унікальні, тобто можливі кратні ребра. Існує інше, більш коректне визначення: граф визначається як трійка G=(V,E,), де V - безліч вершин, E - безліч ребер, а =(v,u,e) - тримісний предикат (булевська функція від трьох перемінних), що повертає True тоді і тільки тоді, коли ребро e інцидентне вершинам v і u. Однак такі "строгості" у нашому викладі є надмірними. Якщо порядок елементів, що входять у ei, має значення, то граф називається орієнтованим (directed graph), скорочено - орграф (digraph), інакше - неорієнтованим (undirected graph). Ребра орграфа називаються дугами (arcs). Надалі будемо вважати, що термін "граф", застосовуваний без уточнень "орієнтований" чи "неорієнтований", позначає неорієнтований граф. Приклад: G=(V,E); V={1,2,3,4}; E=<(1,1), (1,2), (1,3), (2,4), (2,4)>
  G Якщо e=(v,u), те вершини v і u називаються кінцями ребра. При цьому говорять, що ребро e є суміжним (інцидентним) кожної з вершин v і u. Вершини v і u також називаються суміжними (інцидентними). У загальному випадку, допускаються ребра виду e=(v,v); такі ребра називаються петлями. Ступінь вершини графа - це число ребер, інцидентни...